|
|
Knihovna pro konečné automaty a převodníky
Bieliková, Michaela ; Lengál, Ondřej (oponent) ; Hruška, Martin (vedoucí práce)
Konečné automaty majú široké uplatnenie v informatike, okrem iných vo formálnej verifikácii, modelovaní systémov a spracovaní prirodzeného jazyka. Avšak modely skutočne reprezentujúce realitu bývajú veľmi komplikované a môžu byť definované nad veľkými, v niektorých prípadoch až nekonečnými, abecedami, a teda môžu obsahovať veľký počet prechodov. V týchto prípadoch nemusí byť je použitie algoritmov na prácu s konečnými automatmi efektívne. Symbolické automaty poskytujú stručnejší zápis tak, že namiesto symbolov v prechodoch používajú predikáty. Konečné prevodníky tiež majú široké uplatnenie, od ligvistiky až po formálnu verifikáciu. Symbolické prevodníky nahradzujú symboly dvojicou predikátov - jeden predikát pre vstupné symboly a jeden pre výstupné. Cieľom tejto práce je návrh knižnice pre klasické a symbolické automaty a prevodníky, ktorá bude vhodná na rýchle prototypovanie nových algoritmov.
|
|
|
Klávesnice pomocí pohledu
Sznapka, Jakub ; Herout, Adam (oponent) ; Hradiš, Michal (vedoucí práce)
Cílem bakalářská práce je vytvoření nástroje pro psaní pohledem. Zabývá se problematikou snímání pohledu a jeho vyhodnocováním. Obsahuje popis metody Swype, která se používá při psaní na dotykových displejích. Následuje rozbor různých způsobů, pomocí kterých je možné modelovat jazyk, který nástroj používá. Hlavní část práce se věnuje samotnému návrhu nástroje, jenž umožňuje psaní pohledem a jeho implementaci za pomoci toolkitu Kaldi.
|
|
|
Korektor diakritiky
Veselý, Lukáš ; Sumec, Stanislav (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem předkládané práce je návrh a implementace aplikace, umožňující doplňování a naopak odstranění diakritiky v česky psaném textu. Popsána je použitá vyhledávací struktura trie a její vztah s konečnými automaty. Dále je předveden algoritmus minimalizace konečného automatu a diskutovány různé metody pro doplňování diakritiky. V praktické části je uvedena samotná implementace programu v programovacím jazyce Java s využitím objektově orientovaného přístupu. Na závěr je provedeno vyhodnocení a analýza dosažených výsledků.
|
|
|
Morfologický analyzátor pomocí konečných automatů
Bezák, Jakub ; Schwarz, Petr (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem tohoto textu je čtenáři co nejvíc přiblížit problematiku morfologie a morfologické analýzy slovenského jazyka s využitím morfologického analyzátoru a nastínit odlišnost od různých světových jazyků. Text také objasňuje význam hledání základního tvaru slov při analýze slovenských textů. V další části se věnuje optimálnímu uložení rozsáhlých slovníků pomocí konečných automatů s využitím jejich minimalizace. Nakonec jsou srovnáváný různé formy implementace.
|
|
|
Efficient Reduction of Finite Automata
Molnárová, Veronika ; Havlena, Vojtěch (oponent) ; Lengál, Ondřej (vedoucí práce)
A finite state automaton is a mathematical model used to describe a machine that performs a computation on the given input over a series of states. In the last century, it has found many uses in different fields of information technology, from video game character behavior to compilers. While each automaton denotes its language, one language can be represented by an infinite number of different automata. As these automata vary in size, to ensure the most efficient work with them, we want to find the smallest one possible. In this thesis, we are going to look at five different types of automata reductions. Firstly, we will talk about three known reduction algorithms, which are the minimization of deterministic automata, the reduction based on a relation of simulation, and the reduction by transformation into a canonical residual automaton. These reductions were implemented in C++ and tested on a sample set of automata to compare their results. Lastly, we looked at the possibility of reducing finite state automata using Boolean satisfiability problem (SAT) and quantified Boolean formula (QBF) solvers. We are presenting a set of rules for each solver for generating a clause in conjunctive normal form (CNF), which can precisely represent the given automaton in Boolean algebra. We used this fact to create a new method of nondeterministic automata reduction.
|
|
|
Knihovna pro konečné automaty a převodníky
Bieliková, Michaela ; Lengál, Ondřej (oponent) ; Hruška, Martin (vedoucí práce)
Konečné automaty majú široké uplatnenie v informatike, okrem iných vo formálnej verifikácii, modelovaní systémov a spracovaní prirodzeného jazyka. Avšak modely skutočne reprezentujúce realitu bývajú veľmi komplikované a môžu byť definované nad veľkými, v niektorých prípadoch až nekonečnými, abecedami, a teda môžu obsahovať veľký počet prechodov. V týchto prípadoch nemusí byť je použitie algoritmov na prácu s konečnými automatmi efektívne. Symbolické automaty poskytujú stručnejší zápis tak, že namiesto symbolov v prechodoch používajú predikáty. Konečné prevodníky tiež majú široké uplatnenie, od ligvistiky až po formálnu verifikáciu. Symbolické prevodníky nahradzujú symboly dvojicou predikátov - jeden predikát pre vstupné symboly a jeden pre výstupné. Cieľom tejto práce je návrh knižnice pre klasické a symbolické automaty a prevodníky, ktorá bude vhodná na rýchle prototypovanie nových algoritmov.
|
|
|
Klávesnice pomocí pohledu
Sznapka, Jakub ; Herout, Adam (oponent) ; Hradiš, Michal (vedoucí práce)
Cílem bakalářská práce je vytvoření nástroje pro psaní pohledem. Zabývá se problematikou snímání pohledu a jeho vyhodnocováním. Obsahuje popis metody Swype, která se používá při psaní na dotykových displejích. Následuje rozbor různých způsobů, pomocí kterých je možné modelovat jazyk, který nástroj používá. Hlavní část práce se věnuje samotnému návrhu nástroje, jenž umožňuje psaní pohledem a jeho implementaci za pomoci toolkitu Kaldi.
|
|
|
Morfologický analyzátor pomocí konečných automatů
Bezák, Jakub ; Schwarz, Petr (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem tohoto textu je čtenáři co nejvíc přiblížit problematiku morfologie a morfologické analýzy slovenského jazyka s využitím morfologického analyzátoru a nastínit odlišnost od různých světových jazyků. Text také objasňuje význam hledání základního tvaru slov při analýze slovenských textů. V další části se věnuje optimálnímu uložení rozsáhlých slovníků pomocí konečných automatů s využitím jejich minimalizace. Nakonec jsou srovnáváný různé formy implementace.
|
|
|
Korektor diakritiky
Veselý, Lukáš ; Sumec, Stanislav (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem předkládané práce je návrh a implementace aplikace, umožňující doplňování a naopak odstranění diakritiky v česky psaném textu. Popsána je použitá vyhledávací struktura trie a její vztah s konečnými automaty. Dále je předveden algoritmus minimalizace konečného automatu a diskutovány různé metody pro doplňování diakritiky. V praktické části je uvedena samotná implementace programu v programovacím jazyce Java s využitím objektově orientovaného přístupu. Na závěr je provedeno vyhodnocení a analýza dosažených výsledků.
|
host ::
RSS.